<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Longest Palindromic Subsequence</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="longest-palindromic-subsequence">Longest Palindromic Subsequence</h1>
<h1 id="1-tushar-roy">1. tushar roy</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=_nCsPn7_OgI&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=9">https://www.youtube.com/watch?v=_nCsPn7_OgI&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=9</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/LongestPalindromicSubsequence.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/LongestPalindromicSubsequence.java</a></li>
</ul>
<pre><code class="language-java"><div><span class="hljs-keyword">package</span> com.interview.dynamic;

<span class="hljs-comment">/**
 * Date 08/01/2014
 * <span class="hljs-doctag">@author</span> Tushar Roy
 *
 * Given a string find longest palindromic subsequence in this string.
 *
 * Time complexity - O(n2)
 * Space complexity - O(n2
 *
 * Youtube link - https://youtu.be/_nCsPn7_OgI
 *
 * References
 * http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LongestPalindromicSubsequence</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">calculate1</span><span class="hljs-params">(<span class="hljs-keyword">char</span> []str)</span></span>{
        <span class="hljs-keyword">int</span> T[][] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[str.length][str.length];
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt; str.length; i++){
            T[i][i] = <span class="hljs-number">1</span>;
        }
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> l = <span class="hljs-number">2</span>; l &lt;= str.length; l++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; str.length-l + <span class="hljs-number">1</span>; i++){
                <span class="hljs-keyword">int</span> j = i + l - <span class="hljs-number">1</span>;
                <span class="hljs-keyword">if</span>(l == <span class="hljs-number">2</span> &amp;&amp; str[i] == str[j]){
                    T[i][j] = <span class="hljs-number">2</span>;
                }<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(str[i] == str[j]){
                    T[i][j] = T[i + <span class="hljs-number">1</span>][j-<span class="hljs-number">1</span>] + <span class="hljs-number">2</span>;
                }<span class="hljs-keyword">else</span>{
                    T[i][j] = Math.max(T[i + <span class="hljs-number">1</span>][j], T[i][j - <span class="hljs-number">1</span>]);
                }
            }
        }
        <span class="hljs-keyword">return</span> T[<span class="hljs-number">0</span>][str.length-<span class="hljs-number">1</span>];
    }


    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">calculateRecursive</span><span class="hljs-params">(<span class="hljs-keyword">char</span> str[],<span class="hljs-keyword">int</span> start,<span class="hljs-keyword">int</span> len)</span></span>{
        <span class="hljs-keyword">if</span>(len == <span class="hljs-number">1</span>){
            <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
        }
        <span class="hljs-keyword">if</span>(len ==<span class="hljs-number">0</span>){
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        }
        <span class="hljs-keyword">if</span>(str[start] == str[start+len-<span class="hljs-number">1</span>]){
            <span class="hljs-keyword">return</span> <span class="hljs-number">2</span> + calculateRecursive(str,start+<span class="hljs-number">1</span>,len-<span class="hljs-number">2</span>);
        }<span class="hljs-keyword">else</span>{
            <span class="hljs-keyword">return</span> Math.max(calculateRecursive(str, start+<span class="hljs-number">1</span>, len-<span class="hljs-number">1</span>), calculateRecursive(str, start, len-<span class="hljs-number">1</span>));
        }
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span></span>{
        LongestPalindromicSubsequence lps = <span class="hljs-keyword">new</span> LongestPalindromicSubsequence();
        String str = <span class="hljs-string">"agbdba"</span>;
        <span class="hljs-keyword">int</span> r1 = lps.calculateRecursive(str.toCharArray(), <span class="hljs-number">0</span>, str.length());
        <span class="hljs-keyword">int</span> r2 = lps.calculate1(str.toCharArray());
        System.out.print(r1 + <span class="hljs-string">" "</span> + r2);
    }
    
}
</div></code></pre>
<h1 id="2-leetcode-516-longest-palindromic-subsequence">2. leetcode 516 Longest Palindromic Subsequence</h1>
<h1 id="21-dp">2.1 dp</h1>
<p>dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j) otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])</p>
<pre><code class="language-python"><div>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestPalindromeSubseq</span><span class="hljs-params">(self, s: str)</span> -&gt; int:</span>
        n = len(s)
        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(<span class="hljs-number">0</span>, n):
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                
                j = i+k
                <span class="hljs-comment">#print(f"i={i} j={j}")</span>
                <span class="hljs-keyword">if</span> j &gt; n:
                    <span class="hljs-keyword">break</span>
                
                <span class="hljs-keyword">if</span> k == <span class="hljs-number">0</span>:
                    dp[i][j] = <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">if</span> s[i<span class="hljs-number">-1</span>] == s[j<span class="hljs-number">-1</span>]:
                        dp[i][j] = <span class="hljs-number">2</span> + dp[i+<span class="hljs-number">1</span>][j<span class="hljs-number">-1</span>]
                    <span class="hljs-keyword">else</span>:
                        dp[i][j] = max(dp[i+<span class="hljs-number">1</span>][j], dp[i][j<span class="hljs-number">-1</span>])
        <span class="hljs-keyword">return</span> dp[<span class="hljs-number">1</span>][n]

</div></code></pre>
<h1 id="22-还可以逐行遍历但必须从下往上">2.2 还可以逐行遍历，但必须从下往上。</h1>
<p>下面是排名第一的算法. dp被缩减为一行向量，而不是矩阵</p>
<pre><code class="language-python"><div><span class="hljs-comment"># 更有趣的DAG</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestPalindromeSubseq</span><span class="hljs-params">(self, s)</span>:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        <span class="hljs-comment">#Speed Up in Leetcode</span>
        <span class="hljs-keyword">if</span> s == <span class="hljs-string">"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"</span>:
            <span class="hljs-keyword">return</span> len(s)<span class="hljs-number">-2</span>

        <span class="hljs-keyword">if</span> s == s[::<span class="hljs-number">-1</span>]:
            <span class="hljs-keyword">return</span> len(s)

        n = len(s)
        dp = [<span class="hljs-number">0</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n)]
        <span class="hljs-comment">#dp[n-1] = 1</span>

        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):   
            newdp = dp[:]
            newdp[i] = <span class="hljs-number">1</span>
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i+<span class="hljs-number">1</span>, n):
                <span class="hljs-keyword">if</span> s[i] == s[j]:
                    newdp[j] = <span class="hljs-number">2</span> + dp[j<span class="hljs-number">-1</span>]
                <span class="hljs-keyword">else</span>:
                    newdp[j] = max(dp[j], newdp[j<span class="hljs-number">-1</span>])
            dp = newdp
                    
        <span class="hljs-keyword">return</span> dp[n<span class="hljs-number">-1</span>]
</div></code></pre>
<h2 id="23-memo递归解法">2.3  memo递归解法</h2>
<p>from functools import lru_cache</p>
<p>class Solution:
def longestPalindromeSubseq(self, s: str) -&gt; int:</p>
<pre><code>    @lru_cache(None)
    def helper(s, i, j):
        if i&gt;j: return 0
        if i==j: return 1
        
        if s[i] == s[j]:
            return 2 + helper(s, i+1, j-1)
        else:
            return max(helper(s, i+1,j), helper(s, i, j-1))
        
    return helper(s, 0, len(s)-1)
</code></pre>

    </body>
    </html>